package medium每日温度;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    //暴力
    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        if (n == 1)
            return new int[1];
        int[] num = new int[n];
        for (int i = 0; i < n-1; i++) {
            int sign = i;
            for (int j = i+1; j < n; j++) {
                if (temperatures[i] < temperatures[j]){
                    num[i] = j-i;
                    break;
                }
            }
        }
        return num;
    }

    //单调栈
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }

}
